package io.vector.study.algorithm.heap;

/**
 * Created by vector on 2017/3/15.
 */
public class MaxHeap<E extends Comparable<? super E>> extends AbstractHeap<E> implements Heap<E> {

    protected void percolateUp(int index) {
        if (index < 1) {
            return ;
        }

        int currentIndex = index;
        int parentIndex = parentIndex(currentIndex);
        while (parentIndex >= 0 && compareByIndex(currentIndex, parentIndex) > 0) {
            swap(currentIndex, parentIndex);
            currentIndex = parentIndex;
            parentIndex = parentIndex(currentIndex);
        }
    }

    protected void percolateDown(int index) {
        int rootIndex = index;
        if (!isValidIndex(rootIndex)) {
            return ;
        }

        int leftChildIndex, rightChildIndex, maxChildIndex;

        while (hasChild(rootIndex)) {
            leftChildIndex = leftChildIndex(rootIndex);
            rightChildIndex = rightChildIndex(rootIndex);
            maxChildIndex = leftChildIndex;

            if (isValidIndex(rightChildIndex) && compareByIndex(rightChildIndex, maxChildIndex) > 0) {
                maxChildIndex = rightChildIndex;
            }

            if (compareByIndex(rootIndex, maxChildIndex) >= 0) {
                break;
            }

            swap(maxChildIndex, rootIndex);
            rootIndex = maxChildIndex;
        }
    }

}
